package tp6;

import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

public class LinearProbingTable<K,V> implements SimpleMap<K,V>{
	private Bucket<K,V>[] buckets;
	private int size=0;
	private int step=1;
	private double loadFactor;
	private static final int MIN_SIZE=3;
	private static final int MIN_STEP=1;
	
	@SuppressWarnings("unchecked")
	public LinearProbingTable(int initialSize, double d){
		if(initialSize<0||d>1){
			throw new IllegalArgumentException();
		}
		
		buckets=new Bucket[Math.max(MIN_SIZE,initialSize)];
		this.step=Math.max(step,MIN_STEP);
		this.loadFactor=d;
	}

	@Override
	public V get(K key) {
		int hash=key.hashCode();
		for(int i=0;true;i++){
			if(buckets[(hash+step*i)%size]!=null){
				if(buckets[(hash+step*i)%size].key.equals(key)){
					return buckets[(hash+step*i)%size].value;
				}
			}
		}
	}

	@Override
	public Set<K> keySet() {
		Set<K> set=new HashSet<K>();
		for(Bucket<K,V>b:buckets){
			set.add(b.key);
		}
		return set;
	}

	@Override
	public void put(K key, V value) {
		if(((double)(size+1)/(double)(buckets.length))>=loadFactor){
			resize(buckets.length*2);
		}
		
		int hash=key.hashCode();
		for(int i=0;true;i++){
			if(buckets[(hash+step*i)%buckets.length]==null){
				buckets[(hash+step*i)%buckets.length]=new Bucket<K,V>(key,value);
				size++;
				return;
			}
		}
	}
	
	@SuppressWarnings("unchecked")
	private void resize(int newLength) {
		Bucket<K,V>[] aux=new Bucket[newLength];
		for(Bucket<K,V> b:buckets){
			int hash=b.key.hashCode();
			for(int i=0;true;i++){
				if(aux[(hash+step*i)%aux.length]==null){
					aux[(hash+step*i)%aux.length]=b;
					return;
				}
			}
		}
		buckets=aux;
	}

	@Override
	public void remove(K key) {
		boolean found=false;
		int hash=key.hashCode();
		for(int i=0;!found;i++){
			if(buckets[(hash+step*i)%buckets.length]!=null){
				if(buckets[(hash+step*i)%buckets.length].key.equals(key)){
					buckets[(hash+step*i)%buckets.length]=null;
					found=true;
					size--;
				}
			}
		}
		
		if(((double)(size)/(double)(buckets.length))>=loadFactor){
			resize(buckets.length/2);
		}
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public Collection<V> values() {
		Set<V> set=new HashSet<V>();
		for(Bucket<K,V> b:buckets){
			set.add(b.value);
		}
	
		return set;
	}
	
	static class Bucket<S,T>{
		S key;
		T value;
		
		Bucket(S key,T value){
			this.key=key;
			this.value=value;
		}
	}

}
